package q542_updateMatrix;

import java.util.Arrays;

public class Solution_1 {
    /*
    考虑一个在m * n矩阵中的某一个点为1
    如果其要到达最近的0节点
    有四种可能：
    水平向左+垂直向上
    水平向左+垂直向下
    水平向右+垂直向上
    水平向右+垂直向下
    我们分别考虑四种情况的动态规划 就能够得到每个节点的最短距离
    比如 假设这个点只能够水平向左+垂直向上
    那么当该节点是0时 距离就是0
    否则就是f(i, j) = Math.min(f(i, j), 1 + Math.min(f(i - 1, j), f(i, j - 1)))
    通过遍历矩阵数次 即可得到答案
    *注 实际上只需要计算左上 和 右下两个方向就能够得到答案
     */
    public int[][] updateMatrix(int[][] mat) {
        int[][] result = new int[mat.length][mat[0].length];
        for (int[] ints : result) {
            // 先用很大的数填充
            Arrays.fill(ints, Integer.MAX_VALUE / 2);
        }

        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] == 0) {
                    result[i][j] = 0;
                }
            }
        }
        
        // 动态规划
        // 我们简化答案为两个方向
        // 1 向右下进行动态规划
        for (int i = 0; i < mat.length ; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (i > 0) {
                    result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
                }
                if (j > 0) {
                    result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
                }
            }
        }
//        // 2 左下
//        for (int i = mat.length - 1; i >= 0 ; i--) {
//            for (int j = 0; j < mat[0].length; j++) {
//                if (i < mat.length - 1) {
//                    result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
//                }
//                if (j > 0) {
//                    result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
//                }
//            }
//        }
//        // 3 右上
//        for (int i = 0; i < mat.length ; i++) {
//            for (int j = mat[0].length - 1; j >= 0; j--) {
//                if (i > 0) {
//                    result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
//                }
//                if (j < mat[0].length - 1) {
//                    result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
//                }
//            }
//        }
        // 4 左上
        for (int i = mat.length - 1; i >= 0 ; i--) {
            for (int j = mat[0].length - 1; j >= 0; j--) {
                if (i < mat.length - 1) {
                    result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
                }
                if (j < mat[0].length - 1) {
                    result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
                }
            }
        }
        return result;
    }
}
